package com.demo101_检查二叉树是否对称;

import java.util.ArrayDeque;

/**
 * 不过这样还是有问题的, 因为这个可能存在这个 虽然不对称,但是结果仍然是 对称的情况
 *
 *
 * 日:  还是有问题呀......   3, null     3 , null    一样儿的问题
 *
 * 最后的还是有一点问题, 算了罢
 */

public class Solution_层序遍历_回文串 {
    public boolean isSymmetric(TreeNode root) {
        if (root==null){
            return false;
        }

        TreeNode pr = root.right;
        TreeNode pl = root.left;
        ArrayDeque<TreeNode> Lqueue = new ArrayDeque<>();
        ArrayDeque<TreeNode> Rqueue = new ArrayDeque<>();
        if (pl==null&&pr==null){
            return true;
        }
        if ((pl==null&&pr!=null)||(pl!=null&&pr==null)){
            return false;
        }
        Lqueue.add(pl);
        Rqueue.add(pr);
        while (Lqueue.size()!=0||Rqueue.size()!=0){
            int lsize=Lqueue.size();
            int rsize = Rqueue.size();

            if (lsize!=rsize){
                return false;
            }

            StringBuilder ls = new StringBuilder();
            for (int i = 0; i < lsize; i++) {
                TreeNode pop = Lqueue.pop();
                ls.append(pop.val);
                if (pop.left!=null){
                    Lqueue.add(pop.left);
                }else {
                    Lqueue.add(new TreeNode(101));
                }
                if (pop.right!=null){
                    Lqueue.add(pop.right);
                }else {
                    Lqueue.add(new TreeNode(101));
                }
            }
            StringBuilder rs=new StringBuilder();
            for (int i = 0; i < rsize; i++) {
                TreeNode pop = Rqueue.pop();
                rs.append(pop.val);

                if (pop.right!=null){
                    Rqueue.add(pop.right);
                }else {
                    Lqueue.add(new TreeNode(101));
                }

                if (pop.left!=null) {
                    Rqueue.add(pop.left);
                }else {
                    Lqueue.add(new TreeNode(101));
                }
            }

            if (!ls.toString().equals(rs.toString())){
                return false;
            }

        }

        return true;
    }


}
